/*
OpenMVL Matrix Vector Library
Copyright (c) 2009 FluidInteractive (R)
 
This software is provided 'as-is', without any express or implied warranty.
In no event will the authors be held liable for any damages arising
from the use of this software.
Permission is granted to anyone to use this software for any purpose,
including commercial applications, and to alter it and redistribute it freely,
subject to the following restrictions:
 
1. The origin of this software must not be misrepresented; you must
not claim that you wrote the original software. If you use this
software in a product, an acknowledgment in the product documentation
would be appreciated but is not required.
2. Altered source versions must be plainly marked as such, and must
not be misrepresented as being the original software.
3. This notice may not be removed or altered from any source distribution.
 
Written by: Nicola Candussi <nicola@fluidinteractive.com>
*/

//meta.hpp

#ifndef MVL_META_HPP
#define MVL_META_HPP

namespace mvl {

namespace meta {

struct none {};
struct void_ {};

template<typename T> struct next { typedef typename T::next type; };
template<typename T> struct prior { typedef typename T::prior type; };

template<int Val>
struct int_ 
{
    enum { value = Val };
    typedef int_<Val>       type;
    typedef int             value_type;
    typedef int_<Val + 1>   next;
    typedef int_<Val - 1>   prior;
    operator int() const    { return Val;  }
};

template<bool Val>
struct bool_ 
{
    enum { value = Val };
    typedef bool_<Val>      type;
    typedef bool            value_type;
    operator bool() const   { return Val;  }
};

//same type
template<typename T1, typename T2> struct is_same : bool_<false> {};
template<typename T> struct is_same<T, T> : bool_<true> {};

//comparisons
template<typename T1, typename T2> struct equal_to;
template<int N1, int N2> 
struct equal_to<int_<N1>, int_<N2> > : bool_<(N1 == N2)> {};

template<typename T1, typename T2> struct not_equal_to;
template<int N1, int N2> 
struct not_equal_to<int_<N1>, int_<N2> > : bool_<(N1 != N2)> {};

template<typename T1, typename T2> struct greater;
template<int N1, int N2> 
struct greater<int_<N1>, int_<N2> > : bool_<(N1 > N2)> {};

template<typename T1, typename T2> struct greater_equal;
template<int N1, int N2> 
struct greater_equal<int_<N1>, int_<N2> > : bool_<(N1 >= N2)> {};

template<typename T1, typename T2> struct less;
template<int N1, int N2> 
struct less<int_<N1>, int_<N2> > : bool_<(N1 < N2)> {};

template<typename T1, typename T2> struct less_equal;
template<int N1, int N2> 
struct less_equal<int_<N1>, int_<N2> > : bool_<(N1 <= N2)> {};

//booleans
template<typename T1, typename T2> struct or_;
template<bool B1, bool B2> 
struct or_<bool_<B1>, bool_<B2> > : bool_<(B1 || B2)> {};

template<typename T1, typename T2> struct and_;
template<bool B1, bool B2> 
struct and_<bool_<B1>, bool_<B2> > : bool_<(B1 && B2)> {};

template<typename T> struct not_;
template<bool B> 
struct not_<bool_<B> > : bool_<(!B)> {};

//arithmetic operations
template<typename T1, typename T2, typename T3 = none> struct plus;
template<int N1, int N2> struct plus<int_<N1>, int_<N2> > : int_<N1 + N2> { };  
template<int N1, int N2, int N3> struct plus<int_<N1>, int_<N2>, int_<N3> > : int_<N1 + N2 + N3> { };  

template<typename T1, typename T2, typename T3 = none> struct minus;
template<int N1, int N2> struct minus<int_<N1>, int_<N2> > : int_<N1 - N2> { };  
template<int N1, int N2, int N3> struct minus<int_<N1>, int_<N2>, int_<N3> > : int_<N1 - N2 - N3> { };  

template<typename T1, typename T2> struct multiplies;
template<int N1, int N2> struct multiplies<int_<N1>, int_<N2> > : int_<N1 * N2> { };  

template<typename T1, typename T2> struct divides;
template<int N1, int N2> struct divides<int_<N1>, int_<N2> > : int_<N1 / N2> { };  

template<typename T1, typename T2> struct shift_left;
template<int N1, int N2> struct shift_left<int_<N1>, int_<N2> > : int_<(N1 << N2)> { };  

template<typename T1, typename T2> struct shift_right;
template<int N1, int N2> struct shift_right<int_<N1>, int_<N2> > : int_<(N1 >> N2)> { };  

//conditionals
template<typename C,typename T1, typename T2> struct if_;
template<typename T1, typename T2> struct if_<bool_<true>, T1, T2> { typedef T1 type; };
template<typename T1, typename T2> struct if_<bool_<false>, T1, T2> { typedef T2 type; };
template<typename C, typename T1, typename T2> struct eval_if: if_<C, T1, T2>::type { };

//min/max
template<typename T1, typename T2> struct min : if_<typename less<T1, T2>::type, T1, T2> { };
template<typename T1, typename T2> struct max : if_<typename greater<T1, T2>::type, T1, T2> { };

//
template<typename T>
struct identity { typedef T type; };

//SEQUENCES

//size of a sequence
template<typename Tag> struct size_impl;

template<typename Sequence>
struct size: size_impl<typename Sequence::tag>::template apply<Sequence> { };

//at
template<typename Tag> struct at_impl;

template<typename Sequence, typename N>
struct at: at_impl<typename Sequence::tag>::template apply<Sequence, N> { };

//clear
template<typename Tag> struct clear_impl;

template<typename Sequence>
struct clear: clear_impl<typename Sequence::tag>::template apply<Sequence> { };

//push_front
template<typename Tag> struct push_front_impl;

template<typename Sequence, typename T>
struct push_front: push_front_impl<typename Sequence::tag>::template apply<Sequence, T> { };

//push_back
template<typename Tag> struct push_back_impl;

template<typename Sequence, typename T>
struct push_back : push_back_impl<typename Sequence::tag>::template apply<Sequence, T> { };

//replace element
template<typename Tag> struct replace_element_impl;

template<typename Sequence, typename Pos, typename NewT>
struct replace_element : replace_element_impl<typename Sequence::tag>::template apply<Sequence, Pos, NewT> { }; 

//iterators
struct random_access_iterator_tag {};

template<typename It> struct deref;
template<typename It, typename N> struct advance;
template<typename It1, typename It2> struct distance;

//begin
template<typename Tag> struct begin_impl;

template<typename Sequence>
struct begin: begin_impl<typename Sequence::tag>::template apply<Sequence> { };

//end
template<typename Tag> struct end_impl;

template<typename Sequence>
struct end: end_impl<typename Sequence::tag>::template apply<Sequence> { };

//
template<typename First, typename Last, typename State, typename BinaryOp>
struct iter_fold 
{
    typedef typename equal_to<First, Last>::type is_done;
    typedef typename eval_if<
        is_done,
        identity<none>,
        typename BinaryOp::template apply<State, First>
    >::type next_apply; 
    typedef typename eval_if<
        is_done,
        identity<none>,
        next<First>
    >::type next_it;

    typedef typename eval_if<
        is_done,
        identity<State>,
        iter_fold<
            next_it,
            Last,
            next_apply,
            BinaryOp
        >
    >::type type;
};

//loop while State::condition is bool_<true>, return the updated state
template<typename State, typename Update>
struct while_ {
    typedef typename eval_if<
        typename State::condition,
        typename Update::template apply<State>,
        State
    >::type updated_state;

    typedef typename eval_if<
        typename State::condition,
        while_<
            updated_state,
            Update
        >,
        identity<State>
    >::type type;
};

template<typename It, typename End, typename F>
inline void for_each(F f, bool_<false>) { }

template<typename It, typename End, typename F>
inline void for_each(F f, bool_<true>) {
    f(typename deref<It>::type());
    typedef typename next<It>::type next_it;
    for_each<next_it, End>(f, typename not_equal_to<next_it, End>::type());
}

template<typename Begin, typename End, typename F>
inline void for_each(F f) {
    for_each<Begin, End>(f, typename not_equal_to<Begin, End>::type());
}

template<typename First, typename Last, typename Val, typename Compare>
struct lower_bound 
{
    //condition Compare(middle, Val)
    template<typename Condition, typename F, typename Len, typename Middle, typename Half> struct left_right;
    //loop for len > 0
    template<typename Condition, typename F, typename Len> struct lower_bound_impl;

    template<typename F, typename Len, typename Middle, typename Half>
    struct left_right<bool_<true>, F, Len, Middle, Half>
    {
        typedef typename minus<Len, Half, int_<1> >::type len;
        typedef typename lower_bound_impl<
            typename greater<len, int_<0> >::type,
            typename next<Middle>::type,
            len
        >::type type;
    };

    template<typename F, typename Len, typename Middle, typename Half>
    struct left_right<bool_<false>, F, Len, Middle, Half> : 
        lower_bound_impl< 
            typename greater<Half, int_<0> >::type,
            F,
            Half
        >
    { };

    template<typename F, typename Len>
    struct lower_bound_impl<bool_<true>, F, Len>
    {
        typedef typename shift_right<Len, int_<1> >::type half;
        typedef typename advance<F, half>::type middle;
        typedef typename Compare::template apply<typename deref<middle>::type, Val>::type condition;
        typedef typename left_right<condition, F, Len, middle, half>::type type;
    };

    template<typename F, typename Len>
    struct lower_bound_impl<bool_<false>, F, Len> : F { };

    //
    typedef typename distance<First, Last>::type len;
    typedef typename lower_bound_impl<
        typename greater<len, int_<0> >::type,
        First, len
    >::type type;
};

//returns an iterator pointing to the element, or Last if such element is not present
template<typename First, typename Last, typename Val, typename Compare>
struct binary_search 
{
    typedef typename lower_bound<First, Last, Val, Compare>::type lb;
    typedef typename equal_to<lb, Last>::type past_end;
    typedef typename eval_if<
        past_end,
        identity<none>,
        deref<lb>
    >::type value; 
    typedef typename eval_if<
        past_end,
        identity<bool_<true> >,
        typename Compare::template apply<Val, value>
    >::type compare;

    typedef typename if_<
        past_end,
        Last,
        typename if_<
            compare,
            Last,
            lb
        >::type
    >::type type;
};

} //namespace meta

} //namespace mvl

#endif
